/*
题目描述
设计一个简单版的最近使用缓存模型。缓存空间有容量限制，时间复杂度要求是理论O(1)，key和value的类型可以是任意类型。
其中“最近使用”是指最近被访问过
对cache的操作有：添加(put (key, value))、查找(get(key))、替换(put (key, value))，
因有容量限制，还需有私有的删除方法，每次当put时，如果容量满，将最久未使用的节点删除。

设LRU<Integer,String>
输入最近访问列表的容量 和 操作次数
put(key,value)时为插入对象key,value
get(key)时为当年前最近访问列表对象的输出
如果存在则输出，不存在输出null

Input Format
第一行为最大容量n和操作次数m
随后m行，put代表输入，使用key,value方式，不同值使用;隔开。
get跟随1个或多个数字用于返回得到的value值，不存在输出null

Input Example
4 4
put 1,value1;2,value2;3,value3;4,value4;5,value 5
get 1;2
put 6,value;4,value44;
get 3;4

Output Format
每个get输出一行

Output Example
null;value2;
null;value44;
 */
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev;
    Node<K, V> next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> map;
    private Node<K, V> head;
    private Node<K, V> tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            return null;
        }
        // 移动节点到头部
        removeNode(node);
        addToHead(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            // 更新值并移动到头部
            node.value = value;
            removeNode(node);
            addToHead(node);
        } else {
            if (map.size() >= capacity) {
                // 删除尾部节点
                Node<K, V> last = tail.prev;
                removeNode(last);
                map.remove(last.key);
            }
            // 添加新节点
            Node<K, V> newNode = new Node<>(key, value);
            map.put(key, newNode);
            addToHead(newNode);
        }
    }

    private void addToHead(Node<K, V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符

        LRUCache<Integer, String> cache = new LRUCache<>(n);

        for (int i = 0; i < m; i++) {
            String line = scanner.nextLine().trim();
            String[] parts = line.split(" ", 2);
            String command = parts[0];

            if (command.equals("put")) {
                String[] entries = parts[1].split(";");
                for (String entry : entries) {
                    String[] kv = entry.split(",", 2);
                    if (kv.length == 2) {
                        int key = Integer.parseInt(kv[0]);
                        String value = kv[1];
                        cache.put(key, value);
                    }
                }
            } else if (command.equals("get")) {
                String[] keys = parts[1].split(";");
                StringBuilder sb = new StringBuilder();
                for (String keyStr : keys) {
                    int key = Integer.parseInt(keyStr);
                    String value = cache.get(key);
                    sb.append(value == null ? "null" : value).append(";");
                }
                System.out.println(sb.toString());
            }
        }
    }
}

//import java.util.Date;
//import java.util.TreeMap;
//
//public class Main<T2 extends Date,T extends TreeMap<String,T2>> {
//    void insert(T map) {
//        map.put("test",(T2)new Date());
//    }
//    public static void main(String[] args) {
//        Main<java.sql.Date,TreeMap<String,java.sql.Date>> l =
//                new Main<java.sql.Date,TreeMap<String,java.sql.Date>>();
//        TreeMap<String,java.sql.Date> tm = new TreeMap<>();
//        l.insert(tm);
//        java.sql.Date t = tm.get("test");
//        System.out.println(t.getClass());
//    }
//}
